#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/7/14 18:13
# ===========================================
#       题目名称： 75. 颜色分类
#       题目地址： https://leetcode.cn/problems/sort-colors/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    def sortColors(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        if nums and len(nums) < 2:
            return nums
        # 左右开弓
        left, right = 0, 1

        while left < right < len(nums):
            if nums[left] > nums[right]:
                nums[left], nums[right] = nums[right], nums[left]
            if right + 1 >= len(nums):
                left += 1
                right = left + 1
            else:
                right += 1

        print(nums)


if __name__ == '__main__':
    s = Solution()
    # [0,0,1,1,2,2]
    s.sortColors(nums=[2, 0, 2, 1, 1, 0])
    # [0,1,2]
    s.sortColors(nums=[2, 0, 1])
